package leetcode.动态规划.simple;

/**
 * @author wangmaolin1
 * @date 2022/1/9 下午8:20
 */
public class _53最大子数组和 {

    /*
        给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        子数组 是数组中的一个连续部分。
     */
    public int maxSubArray(int[] nums) {
        // 1. 记 f(i) = 第 i 个位置结束的最大连续子数组的和
        // 2. 求: max [f(i)] 即计算出每个位置结束的最大连续子数组和，然后找出最大值返回
        // 3. 因为是连续的    因此 f(i)  =  max [f(i)+nums[i],nums[i]],即如果 f(i-1)+当前节点
        //4. 因为每次 f(i)只和 f(i-1) 相关，因此直接用一个变量 p 代表 f(i-1)，每次更新最大值
        if (nums.length==1){
            return nums[0];
        }
        int result = nums[0], p = nums[0];


        for (int num : nums) {
            p = Math.max(p + num, num);
            result = Math.max(result, p);
        }
        return result;
    }

}
